package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

public class 乘积最大子数组 {

        //[-2,3,-4]
    public int maxProduct(int[] nums) {

        //记录以i结尾的连续数组最大值
        int[] dp = new int[nums.length];
        //记录以i结尾的连续数组最小值
        int[] dp2 = new int[nums.length];
        dp[0] = nums[0];
        dp2[0] = nums[0];
//         [-1,-2,-9,-6] [2,-5,-2,-4,3]
        for (int i = 1; i < dp.length; i++) {

            if (nums[i]<0){
                dp2[i] = Math.min(dp[i-1] * nums[i],nums[i]);
                dp[i] = Math.max(dp2[i-1] * nums[i],nums[i]);
            }else {
                dp[i] = Math.max(dp[i-1]*nums[i],nums[i]);
                dp2[i] = Math.min(dp2[i-1]*nums[i],nums[i]);
            }
        }
        int max= Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }

}
